package lcr;

public class Test0154 {
}

class Solution0154_1 {
    public Node copyRandomList(Node head) {
        if (head==null) return null;

        Node now=head;
        while (now !=null){
            Node node=new Node(now.val);
            node.next=now.next;
            now.next=node;
            now=node.next;
        }

        Node ans=head.next;
        now=head;
        while (now !=null){
            Node node = now.next;
            if (now.random!=null)
                node.random=now.random.next;
            now=node.next;
        }

        now=head;
        while (now !=null){
            Node node = now.next;
            now.next=node.next;
            now=now.next;
            if (now!=null)
                node.next=now.next;
        }

        return ans;
    }
}
